The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, and associative memories, including, but not limited to binary content-addressable memories (binary CAMs) and ternary content-addressable memories (ternary CAMs or TCAMs). Each entry of a binary CAM typically includes a value for matching against, while each TCAM entry typically includes a value and a mask. The associative memory compares a lookup word against all of the entries in parallel, and typically generates an indication of the highest priority entry that matches the lookup word. An entry matches the lookup word in a binary CAM if the lookup word and the entry value are identical, while an entry matches the lookup word in a TCAM if the lookup word and the entry value are identical in the bits that are not indicated by the mask as being irrelevant to the comparison operations.
FIGS. 1A-B illustrate one implementation of a prior art content-addressable memory entry 100 and bit cells 101A-B therein. Each bit cell 101A-B includes a storage 105A-B for storing a value to be matched against, which are stored by exerting the read/write line 110 and based on the bit values and their complements on lines 111A-B and 112A-B. In order to determine if content-addressable memory entry 100 matches a lookup word, match line 132 is precharged to Vdd based on precharging signal 120 during a precharging phase of the lookup operation. The bit values (and their complements) of the lookup word are applied on bit lines 111A-B and 1112A-B, which are compared by comparison circuits 130 during a matching phase of the lookup operation to the stored bit values (105A-B). For a ternary content-addressable memory, the comparison operation is typically disabled if the bit cell is programmed with a don't care—as it matches any value of the corresponding bit of the lookup word. If any of the entry bit cells 101A-B determine that they do not match, then match line 132 is discharged by the corresponding comparison circuit(s) 130. Any drop in the voltage of match line 132 is amplified, with any slight change in the voltage of match line 132 quickly detected by match line sense amplifier 135, which provides the corresponding hit/miss indication 136 based on the results of the comparison operations. FIG. 1B illustrates discharge paths 171 for a content-addressable memory entry cell 170 for changing the voltage of match line 132 in response to content-addressable memory entry cell 170 identifying that it does not match.
Associative memories are very useful in performing packet classification operations. As with most any system, errors can occur. For example, array parity errors can occur in certain content-addressable memories as a result of failure-in-time errors which are typical of semiconductor devices.
When a packet classification lookup operation is performed on an associative memory with corrupted entries, a bit error in an entry can result in a false hit, or a false miss. A false hit occurs when the corrupted value of an entry matches the lookup value when it otherwise would not match that entry (and thus another entry or no entry should have been matched). A false miss occurs when an entry should have been matched except for the corruption in the entry. This could result in no entry being matched or another lower-priority entry being matched. When these lookup operations are used for packet classification, an incorrect match or miss presents a problem especially when identifying a route or performing a security classification.
Error-correcting and error-detecting codes are well-known. For example, ANDREW S. TANENBAUM, COMPUTER NETWORKS, Prentice-Hall, 1981, pp. 125-132, discusses error-correcting and error-detecting codes, and is hereby incorporated by reference. Assume a codeword contains n bits of which m are data bits and r are error-correcting or error-detecting bits (e.g., redundant or check bits), with n=m+r. There are many well-known ways to generate the error-detecting and error-correcting bits. Given two codewords, it is possible to determine how many bits differ (e.g., by exclusively-OR'ing or one bit summing the corresponding bits of the two codewords and summing these results). The number of bit positions in which two codewords or a set of codewords differ is called the Hamming distance. A Hamming distance of d, means that it will require d single-bit errors to convert one codeword to another codeword. To detectj errors, a Hamming distance of j+1 is required because with such a code, there is no way that j single-bit errors can change a valid codeword into another valid codeword. Similarly, to correct j errors, a distance 2j+1 code because that way the legal codewords are so far apart that even with j changes, the original codeword is still closer than any other codeword, so it can be uniquely determined.
A prior approach protects the associative memory entries with error detection or correction values when the associative memory is not being used to perform a lookup operation. For example, using a background operation, the associative memory entries are periodically checked and corrected for errors (e.g., read from their location and if an error, the correct value is written back). Another prior approach is to periodically over write each associative memory entry with the correct value. These and other prior approaches do not immediately detect the error, nor detect the error when a lookup operation is performed on the corrupted entry. Thus, there can be significant periods (e.g., several seconds to minutes which can be a very long time in the context of a packet switch) before such corrupted entry is corrected.
Some random access memory (RAM) add error-correcting or error-detecting codes to each memory cell. As part of a read operation of a memory location, the data portion and the error-correcting or error-detecting code is read, which is then used to detect a possible error and/or correct a discovered error in the data portion. This is especially convenient to do as only one set of error-detecting/error correcting circuitry is required (i.e., to operate on the data read from the specified memory location). However, this approach is impractical for an associative memory, as each associative memory entry would need this complete circuitry, and the result of the error-corrected operation for each memory location would need to be compared to the lookup word for every lookup operation.
Shoham et al., “Error Protection for Lookup Operations in Content-Addressable Memory Entries,” U.S. patent application Ser. No. 10/879,254, filed Jun. 29, 2004, is hereby incorporated by reference in its entirety. Shoham et al. discloses techniques for populating content-addressable memory entries with values that have a Hamming distance of n bits and for identifying a matching entry that matches in at least k bit positions, where n>k>0. Other techniques not explicitly disclosed in Shoham et al. for identifying such matching entries could be useful.